#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;


/***
 * 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。



示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
 *
 *
 *
 *todo 这个题一看就是dp
 * // dp[]数组代表递增子序列个数
 * // 递推条件 if(nums[i]>nums[i-1]) dp[i]=dp[i-1] else
 *
 *
 *
 * */

int findNumberOfLIS(vector<int> &nums) {
    if (nums.size() <= 1) return nums.size();

    vector<int> dp(nums.size(), 1);//位置i的最长递增子序列长度
    vector<int> count(nums.size(), 1);//那么以j为结尾的子串的最长递增子序列的个数
    int maxCount = 0;
    for (int i = 1; i < nums.size(); ++i) {

        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    count[i] = count[j];
                } else if (dp[j] + 1 == dp[i]) {
                    count[i] += count[j];
                }

            }
            maxCount = max(maxCount, dp[i]);

        }


    }
    int result = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (maxCount == dp[i]) result += count[i];
    }
    return result;
}
